{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "understanding-sudan",
   "metadata": {},
   "outputs": [],
   "source": [
    "S = \"abcd\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "romance-lying",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'b'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S[1:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "funded-stylus",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [5, 2, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "smart-compact",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr = [(i, v) for i,v in enumerate(arr)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "wrapped-exposure",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 5), (1, 2), (2, 1)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "respiratory-french",
   "metadata": {},
   "outputs": [],
   "source": [
    "arr.sort(key=lambda tup: tup[1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "eight-english",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 1), (1, 2), (0, 5)]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arr"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "clear-drilling",
   "metadata": {},
   "source": [
    "yingshaoxo 牛逼：\n",
    "\n",
    "\n",
    "https://leetcode.com/problems/find-and-replace-in-string\n",
    "\n",
    "\n",
    "Runtime: 40 ms, faster than 50.49% of Python3 online submissions for Find And Replace in String.\n",
    "Memory Usage: 14.5 MB, less than 7.77% of Python3 online submissions for Find And Replace in String.\n",
    "\n",
    "\n",
    "```python\n",
    "‵class Solution:\n",
    "    def findReplaceString(self, S: str, indexes: List[int], sources: List[str], targets: List[str]) -> str:\n",
    "        #7:17\n",
    "        the_order = [(i, v) for i,v in enumerate(indexes)]\n",
    "        the_order.sort(key=lambda tup: tup[1])\n",
    "        new_indexes = []\n",
    "        new_sources = []\n",
    "        new_targets = []\n",
    "        for item in the_order:\n",
    "            i = item[0]\n",
    "            new_indexes.append(indexes[i])\n",
    "            new_sources.append(sources[i])\n",
    "            new_targets.append(targets[i])\n",
    "        indexes = new_indexes\n",
    "        sources = new_sources\n",
    "        targets = new_targets\n",
    "        new_S = \"\"\n",
    "        i_list = []\n",
    "        n = 0\n",
    "        for i, s, t in zip(indexes, sources, targets):\n",
    "            possible_word = S[i:i+len(s)]\n",
    "            if possible_word == s:\n",
    "                if (len(i_list) == 0):\n",
    "                    new_S += S[:i] + t\n",
    "                    #print(new_S)\n",
    "                else:\n",
    "                    last_n = i_list[-1]\n",
    "                    new_S += S[indexes[last_n]+len(sources[last_n]):i] + t\n",
    "                    #print(new_S)\n",
    "                i_list.append(n)\n",
    "            n += 1\n",
    "        if len(i_list):\n",
    "            last_n = i_list[-1]\n",
    "            new_S += S[indexes[last_n]+len(sources[last_n]):] \n",
    "        if new_S == \"\":\n",
    "            return S\n",
    "        return new_S\n",
    "        #7:38\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "burning-population",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}